package leetcode.每日一题;

import org.junit.Test;

import java.util.HashSet;
import java.util.Set;

/**
 * @author ：zsy
 * @date ：Created 2022/10/14 10:14 AM
 * @description：
 */
public class 不同的子序列_II {
    @Test
    public void test() {
        Solution solution = new Solution();
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < 200; i++) {
            builder.append("a");
        }
        System.out.println(solution.distinctSubseqII(builder.toString()));
    }

    class Solution {
        public int distinctSubseqII(String s) {
            int len = s.length();
            int factor = (int) Math.pow(2, len);
            Set<String> set = new HashSet<>();
            for (int i = 1; i < factor; i++) {
                StringBuilder builder = new StringBuilder();
                for (int j = s.length() - 1; j >= 0; j--) {
                    if (((1 << j) & i) != 0) {
                        builder.append(s.charAt(j));
                    }
                }
                set.add(builder.toString());
            }
            return set.size();
        }
    }
}
